import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.*;

import static java.util.Arrays.*;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-05-23
 * Time:11:26
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Algorithms {
    /**
     * 牛客 : 二维数组中的查找
     * 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
     *
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int[][] array) {
        //若数组为空;则返回false
        if (array == null) {
            return false;
        }
        int i = 0;
        int j = array[0].length - 1;
        //从右上角进行遍历,该位置是改行最大,该列最小的值
        while (i < array.length && j >= 0) {
            //target大于该行最大,则行加加
            if (target > array[i][j]) {
                i++;
            } else if (target < array[i][j]) {
                //target小于该行最大,则列减减
                j--;
            } else {
                //找到了
                return true;
            }
        }
        return false;
    }


    /**
     * 牛客 : 替换空格
     *
     * @param str
     * @return
     */
    public String replaceSpace(StringBuffer str) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ' ') {
                ans.append("%20");
            } else {
                ans.append(str.charAt(i));
            }
        }
        return ans.toString();
    }

    /**
     * 牛客 : 从尾到头打印链表
     * 逆置链表 递归 栈 头插法
     *
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        while (listNode != null) {
            ans.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(ans);
        return ans;
    }

    /**
     * 递归
     *
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        printListFromTailToHeadCore(ans, listNode);
        return ans;
    }

    private void printListFromTailToHeadCore(ArrayList<Integer> ans, ListNode listNode) {
        if (listNode == null) {
            return;
        }
        printListFromTailToHeadCore(ans, listNode.next);
        ans.add(listNode.val);
    }

    /**
     * 牛客 : 重建二叉树
     * 根据root节点，将中序vector划分成vin_left，vin_right两部分中序子序列
     * 根据中序子序列长度，将前序vector划分成pre_left, pre_right对应的前序子序列
     * root->left递归生成
     * root->right递归生成
     */

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        if (pre.length == 0 || vin.length == 0) {
            return null;
        }
        return reConstructBinaryTreeCore(pre, 0, pre.length - 1, vin,
                0, vin.length - 1);
    }

    private TreeNode reConstructBinaryTreeCore(int[] pre, int preStart, int preEnd,
                                               int[] vin, int vinStart, int vinEnd) {
        if (preStart > preEnd || vinStart > vinEnd) {
            return null;
        }
        TreeNode root = new TreeNode(pre[preStart]);
        int i = vinStart;
        for (; i <= vinEnd; i++) {
            if (vin[i] == pre[preStart]) {
                root.left = reConstructBinaryTreeCore(pre, preStart + 1, i - vinStart + preStart,
                        vin, vinStart, i - 1);
                root.right = reConstructBinaryTreeCore(pre, i - vinStart + preStart + 1, preEnd,
                        vin, i + 1, vinEnd);
                break;
            }
        }
        return root;
    }

    /**
     * 牛客 : 旋转数组的最小数字
     * 理论上，遍历一次即可，但是我们可以根据题面使用稍微高效且更简单一点的做法
     * 按照要求，要么是一个非递减排序的数组（最小值在最开始），要么是一个旋转(最小值在中间某个地方)
     * 而且，旋转之后有个特征，就是在遍历的时候，原始数组是非递减的，旋转之后，就有可能出现递减，引起递减的数字，就是最小值
     */
    public int minNumberInRotateArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] > array[i + 1]) {
                return array[i + 1];
            }
        }
        return array[0];
    }

    /**
     * 牛客 : 斐波那契数列
     * 迭代方案
     *
     * @param n
     * @return
     */
    public int Fibonacci(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = first + second;
            first = second;
            second = ans;
        }
        return ans;
    }

    /**
     * 牛客 : 跳台阶
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）
     *
     * @param target
     * @return
     */
    public int jumpFloor(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        int ans = 0;
        int first = 1;
        int second = 2;
        for (int i = 3; i <= target; i++) {
            ans = first + second;
            first = second;
            second = ans;
        }
        return ans;
    }

    //递归+动态规划
    public int jumpFloor1(int target) {
        if (target == 1 || target == 2) {
            return target;
        }
        return jumpFloor1(target - 1) + jumpFloor1(target - 2);
    }

    /**
     * 牛客 : 矩形覆盖
     * 解析： 用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，每次放置的时候，无非两种放法，横着放或竖着放
     * 其中，横着放一个之后，下一个的放法也就确定了，故虽然放置了两个矩形，但属于同一种放法
     * 其中，竖着放一个之后，本轮放置也就完成了，也属于一种方法
     * 所以，当2*n的大矩形被放满的时候，它无非就是从上面两种放置方法放置来的
     *
     * @param target
     * @return
     */
    public int rectCover(int target) {
        if (target <= 2) {
            return target;
        }
        return rectCover(target - 1) + rectCover(target - 2);
    }

    /**
     * 牛客 : 二进制中1的个数
     * 输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。
     *
     * @param n
     * @return
     */
    public int NumberOf11(int n) {
        int ans = 0;
        for (int i = 0; i <= 31; i++) {
            if (((n >> i) & 1) == 1) {
                ans++;
            }
        }
        return ans;
    }

    public int NumberOf1(int n) {
        int ans = 0;
        while (n != 0) {
            n = n & (n - 1);
            ans++;
        }
        return ans;
    }

    /**
     * 牛客 : 调整数组顺序使奇数位于偶数前面
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。
     *
     * @param array
     */
    public static void reOrderArray(int[] array) {
        int k = 0;
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1) {//从左向右，每次遇到的，都是最前面的奇数，一定将来要被放在k下标处
                int temp = array[i];//现将当前奇数保存起来
                int j = i;
                while (j > k) {//将该奇数之前的内容(偶数序列)，整体后移一个位置
                    array[j] = array[j - 1];
                    j--;
                }
                array[k++] = temp;//将奇数保存在它将来改在的位置，因为我们是从左往右放的，没有跨越奇 数，所以一定是相对位置不变的
            }
        }
    }

    public static void main1(String[] args) {
        int[] nums = {1, 2, 3, 4};
        reOrderArray(nums);
    }

    /**
     * 链表中倒数第k个结点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode FindKthToTail(ListNode head, int k) {
        if (head == null || k < 0) {
            return null;
        }
        ListNode first = head;
        ListNode second = head;
        while (k > 0 && first != null) {
            k--;
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return k > 0 ? null : second;
    }

    /**
     * 反转链表
     * 给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，
     * 反转该链表后，返回新链表的表头。
     * 1. 定义三个指针，整体右移，边移动，边翻转，保证不会断链。
     * 2. 可以采用头插思想进行翻转
     *
     * @param head
     * @return
     */
    //三指针
    public ListNode ReverseList(ListNode head) {
        //头节点为空或只有头节点
        if (head == null || head.next == null) {
            return head;
        }

        //至少有两个节点
        ListNode next = null;//指向下一个节点
        ListNode pre = null;//指向前一个节点
        ListNode cur = head;//指向当前节点
        while (cur != null) {
            next = cur.next;//先记录当前节点的下一个节点
            cur.next = pre;//修改当前节点的下一个节点的值
            pre = cur;//记录前一个节点的值
            cur = next;//cur往下走一步
        }
        return pre;
    }

    //头插法
    public ListNode ReverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode new_head = null;
        while (head != null) {
            ListNode tmp = head;
            head = head.next;
            tmp.next = new_head;
            new_head = tmp;
        }
        head = new_head;
        return head;
    }

    /**
     * 合并两个排序的链表
     * 输入两个递增的链表，单个链表的长度为n，
     * 合并这两个链表并使新链表中的节点仍然是递增排序的。
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        //记录新链表的头
        ListNode newHead = null;
        //记录新链表的尾
        ListNode newTail = null;
        //任一为空都跳出循环
        while (list1 != null && list2 != null) {
            //比较;找出比较小的节点
            ListNode tmp = list1.val < list2.val ? list1 : list2;
            //节点较小的链表向下走一步
            if (tmp == list1) {
                list1 = list1.next;
            } else {
                list2 = list2.next;
            }
            //第一次插入
            if (newHead == null) {
                newHead = tmp;
                newTail = tmp;
            } else {
                //不是第一次插入
                newTail.next = tmp;
                newTail = newTail.next;
            }
        }
        //任一链表为空;新链表连接不为空的链表
        if (list1 == null) {
            newTail.next = list2;
        } else {
            newTail.next = list1;
        }
        return newHead;
    }

    /**
     * 树的子结构
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
     *
     * @param root1
     * @param root2
     * @return
     */
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //第一步，先确定起始比较位置
        if (root1 == null || root2 == null) {
            return false;
        }

        boolean ans = false;
        //确立起始比较位置,从该位置尝试比较
        if (root1.val == root2.val) {
            ans = isSameFromBegin(root1, root2);
        }
        //说明root1.val != root2.val or 上面的起始位置不满足需求，换一个起始位置
        if (ans != true) {//在左子树中找找
            ans = HasSubtree(root1.left, root2);
        }
        if (ans != true) {//在右子树中找找
            ans = HasSubtree(root1.right, root2);
        }
        return ans;
    }

    private boolean isSameFromBegin(TreeNode root1, TreeNode root2) {
        if (root2 == null) {//roo2为null，说明已经比较完了
            return true;
        }
        if (root1 == null) { //root1为空，说明beginSub不是你的子树
            return false;
        }
        if (root1.val != root2.val) {//说明整树中，有不相等的节点
            return false;
        }
        //分别比较左右左右子树，必须都是相等的
        return isSameFromBegin(root1.left, root2.left) && isSameFromBegin(root1.right, root2.right);
    }

    /**
     * 镜像二叉树
     * 操作给定的二叉树，将其变换为源二叉树的镜像
     *
     * @param root
     */
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror(root.left);
        Mirror(root.right);
    }

    /**
     * 牛客 : 删除链表中重复的结点
     *
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }

        ListNode newHead = new ListNode(0);
        newHead.next = pHead;

        ListNode prev = newHead;
        ListNode last = pHead;
        while (last != null) {
            //节点不重复;prev跟last都向前走一步;直至链表尾
            while (last.next != null && last.val != last.next.val) {
                prev = prev.next;
                last = last.next;
            }
            //节点重复;last走到不重复处停下来或者走到链表尾停下来
            while (last.next != null && last.val == last.next.val) {
                last = last.next;
            }
            //走到这里结果一共有三种,注意：prev永远指向的是前驱有效起始节点：
            // 1. last.next != null 并且 (prev, last] 限定了一段重复范围，此时进行去重
            // 2. last.next == null && (prev, last] 限定了一段重复范围，此时进行去重，最后相当于prev- >next = nullptr
            // 3. last.next == null && prev.next == last,这说明，从本次循环开始，大家都不相同，就不需 要进行去重，这个是特殊情况
            if (prev.next != last) {
                prev.next = last.next;
            }
            last = last.next;
        }
        return newHead.next;
    }

    /**
     * 包含min函数的栈--最小栈
     *
     * @param node
     */
    private Stack<Integer> dataStack = new Stack<>();
    //维护一个最小栈
    private Stack<Integer> minStack = new Stack<>();

    public void push(int node) {
        dataStack.push(node);
        if (minStack.empty() || node < minStack.peek()) {
            minStack.push(node);
        } else {
            minStack.push(minStack.peek());
        }
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    public int top() {
        return dataStack.peek();
    }

    public int min() {
        return minStack.peek();
    }

    /**
     * 栈的压入、弹出序列-第二个序列是否可能为该栈的弹出顺序
     *
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        if (popA == null || pushA == null || popA.length == 0 || pushA.length == 0) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        for (; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (!stack.isEmpty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    /**
     * 从上往下打印二叉树--层序变量二叉树-利用队列(Queue)
     *
     * @param root
     * @return
     */
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {

            TreeNode cur = queue.poll();
            ans.add(cur.val);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
        return ans;
    }

    /**
     * 二叉搜索树的后序遍历序列
     *
     * @param sequence
     * @return
     */
    public boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence.length == 0) {
            return false;
        }
        return VerifySquenceOfBSTCore(sequence, 0, sequence.length - 1);
    }

    private boolean VerifySquenceOfBSTCore(int[] sequence, int start, int end) {
        //在不断查找过程中，区域不断缩小，为空时，证明之前的所有范围都满足检测条件
        // 也就是是一个BST
        if (start >= end) {
            return true;
        }
        //拿到root节点的值
        int root = sequence[end];
        //先遍历左半部分，也就是整体都要比root小，拿到左子树序列
        int i = start;
        while (i < end && sequence[i] < root) {
            i++;
        }
        //在检测右子树是否符合大于root的条件,要从i开始，也就是右半部分的开始
        for (int j = i; j < end; j++) {
            if (sequence[j] < root) {
                return false;
            }
        }
        //走到这里，就说明，当前序列满足需求。但并不代表题目被解决了，还要在检测left和right各自是否也满 足
        return VerifySquenceOfBSTCore(sequence, start, i - 1) && VerifySquenceOfBSTCore(sequence, i, end - 1);
    }

    /**
     * 二叉树中和为某一值的路径(二)-回溯算法
     * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
     *
     * @param root
     * @param expectNumber
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        FindPathDFS(root, ans, list, expectNumber);
        return ans;
    }

    private void FindPathDFS(TreeNode root, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> list, int expectNumber) {
        if (root == null) {
            return;
        }
        //将当前值放入list待选结果集中
        list.add(root.val);
        //更新目标值
        expectNumber -= root.val;
        //1. 已经是叶子节点了
        //2. 从root到该叶子节点，之和是expectNumber
        //3. 是叶子节点，但是不满足节点，也不影响，程序会直接退出
        if (root.left == null && root.right == null && expectNumber == 0) {
            ans.add(new ArrayList<>(list));
        }
        FindPathDFS(root.left, ans, list, expectNumber);
        FindPathDFS(root.right, ans, list, expectNumber);
        list.remove(list.size() - 1);
    }

    /**
     * 字符串的排列--回溯算法-DFS
     *
     * @param str
     * @return
     */
    public static ArrayList<String> Permutation(String str) {
        ArrayList<String> ans = new ArrayList<>();
        LinkedList<Character> result = new LinkedList<>();
        boolean[] flag = new boolean[str.length()];
        PermutationDFS(str, ans, result, flag);
        return ans;
    }

    private static void PermutationDFS(String str, ArrayList<String> ans, LinkedList<Character> result, boolean[] flag) {
        if (result.size() == str.length()) {
            StringBuilder builder = new StringBuilder();
            for (Character c : result) {
                builder.append(c);
            }
            //可以用Set去重
            if (ans.contains(builder.toString())) {
                return;
            }
            ans.add(builder.toString());
            builder = new StringBuilder();
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            if (flag[i] == false) {
                flag[i] = true;
                result.add(str.charAt(i));
                PermutationDFS(str, ans, result, flag);
                flag[i] = false;
                //sb.deleteCharAt(sb.length()-1);
                result.removeLast();
            }
        }
    }

    public static void main2(String[] args) {
        System.out.println(Permutation("abc"));
    }

    /**
     * 数组中出现次数超过一半的数字
     *
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int[] array) {
        int ans = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : array) {
            if (map.containsKey(num)) {
                int count = map.get(num);
                count++;
                if (count >= array.length / 2) {
                    ans = num;
                    break;
                }
                map.put(num, count);
            } else {
                map.put(num, 1);
            }
        }
        if (map.size() == 1) {
            return array[0];
        }
        return ans;
    }

    /**
     * 最小的K个数
     * 直接升序排序，取前n个，这个方法不考虑了
     * 优先级堆列
     *
     * @param input
     * @param k
     * @return
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int i = 0; i < input.length; i++) {
            queue.add(input[i]);
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (k > 0) {
            list.add(queue.poll());
            k--;
        }
        return list;
    }

    /**
     * 连续子数组的最大和-动态dp
     *
     * @param array
     * @return
     */
    /**
     * 定义状态# f(i): 以i下标结尾的最大连续子序列的和
     * 状态递推：f(i) = max(f(i-1)+array[i], array[i]) 【这里一定要注意连续关键字】
     * 状态初始化：f(0) = array[0], max = array[0]
     * 以[-2,-3,4,-1,-2,1,5,-3]为例,可以发现,
     * dp[0] = -2
     * dp[1] = -3
     * dp[2] = 4
     * dp[3] = 3
     * 以此类推,会发现: dp[i] = max{dp[i-1]+array[i],array[i]}
     *
     * @param array
     * @return
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            if (dp[i] > max) {
                max = dp[i];
            }
        }
        return max;
    }

    public int FindGreatestSumOfSubArray1(int[] array) {
        int total = array[0];
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (total >= 0) {
                //如果之前total累计的和>=0,说明当前数据+total，有利于整体增大
                total += array[i];
            } else {
                //如果之前累计的和<0,说明当前数据+total，不利于整体增大,丢弃之前的所有值
                // 这里有一个基本事实，就是之前的连续数据和是确定的。
                // 连续，是可以从以前到现在，也可以是从现在到以后。至于要不要加以前，就看以前对整体增大又没有 贡献度
                total = array[i];
            }
            if (max < total) {
                max = total;
            }
        }
        return max;
    }

    /**
     * 回文数索引
     * 可以从两侧进行统计，如果不同，则删除任意一个，在判定是否是回文，
     * 如果是，下标就是删除数据的下标，如果不是，就 是另一个元素的下标
     *
     * @param args
     */
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int nums = scanner.nextInt();
        while (nums > 0) {
            StringBuilder str = new StringBuilder(scanner.next());
            int start = 0;
            int end = str.length() - 1;
            int ans = -1;
            while (start < end) {
                if (str.charAt(start) != str.charAt(end)) {
                    boolean flag = IsPalindrome(start + 1, end, str);
                    if (flag) {
                        ans = start;
                        break;
                    } else {
                        ans = end;
                        break;
                    }
                }
                start++;
                end--;
            }
            System.out.println(ans);
            nums--;
        }
    }

    private static boolean IsPalindrome(int start, int end, StringBuilder str) {
        while (start < end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }


    /**
     * 把数组排成最小的数
     * 对于本题，我们要的有效序列是：序列中任何一个元素y，和它前的任何一个元素x进行有序组合形成 xy，
     * 比和他后面的任何一个元素z进行有效序列组合yz，满足条件xy < yz（采用字典序列排序）
     *
     * @param numbers
     * @return
     */
    public String PrintMinNumber(int[] numbers) {
        if (numbers == null) {
            return new String();
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : numbers) {
            list.add(num);
        }
        Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer x, Integer y) {
                String xs = x + "" + y;
                String ys = y + "" + x;
                return xs.compareTo(ys);
            }
        });
        String result = new String();
        for (Integer num : list) {
            result += num;
        }
        return result;
    }

    /**
     * 两个链表的第一个公共结点
     * 求第一公共节点，本质是让长的链表先走abs（length1-length2）步，
     * 后面大家的步调一致，往后找第一个地址相同的 节点，就是题目要求的节点
     *
     * @param pHead1
     * @param pHead2
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int lengthHead1 = 0;
        ListNode curHead1 = pHead1;
        while (curHead1 != null) {
            lengthHead1++;
            curHead1 = curHead1.next;
        }
        int lengthHead2 = 0;
        ListNode curHead2 = pHead2;
        while (curHead2 != null) {
            lengthHead2++;
            curHead2 = curHead2.next;
        }
        curHead1 = pHead1;
        curHead2 = pHead2;

        if (lengthHead1 > lengthHead2) {
            int tmp = lengthHead1 - lengthHead2;
            while (tmp > 0) {
                curHead1 = curHead1.next;
                tmp--;
            }
        } else {
            int tmp = lengthHead2 - lengthHead1;
            while (tmp > 0) {
                curHead2 = curHead2.next;
                tmp--;
            }
        }
        while (curHead1 != curHead2) {
            curHead1 = curHead1.next;
            curHead2 = curHead2.next;
        }
        return curHead1;
    }


    /**
     * 二叉树深度
     * 1. 可以使用递归方式
     * 2. 可以层序遍历，统计层数，也就是深度or高度-层序遍历利用Queue
     *
     * @param root
     * @return
     */
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right));
    }

    /**
     * 数组中只出现一次的数字
     *
     * @param array
     * @param num1
     * @param num2
     */
    public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
        if (array == null) {
            return;
        }
        HashSet<Integer> set = new HashSet<>();
        for (Integer num : array) {
            if (set.contains(num)) {
                set.remove(num);
            } else {
                set.add(num);
            }
        }
        int i = 0;
        for (Integer a : set) {
            if (i == 0) {
                num1[0] = a;
            } else {
                num2[0] = a;
            }
            i++;
        }
    }

    /**
     * 和为S的连续正数序列-滑动窗口
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        int low = 1;
        int high = 2;
        while (low < high) {
            //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
            // 这里的的low和high不光代表位置，也代表对应的值
            int total = ((low + high) * (high - low + 1)) / 2;
            if (total == sum) {
                ArrayList<Integer> tmp = new ArrayList<>();
                for (int i = low; i <= high; i++) {
                    tmp.add(i);
                }
                ans.add(tmp);
                low++;
            } else if (total < sum) {
                //说明该序列区间中的数据和小于sum，应该扩大区间,以包含更多数据
                high++;
            } else {
                //说明该序列区间中的数据和大于sum，应该缩小区间,以包含较少数据
                low++;
            }
        }
        return ans;
    }

    /**
     * 左旋转字符串
     *
     * @param str
     * @param n
     * @return
     */
    public static String LeftRotateString(String str, int n) {
        if (str.length() <= 1) {
            return str;
        }
        StringBuilder ans = new StringBuilder(str);
        while (n > 0) {
            String s = ans.substring(0, 1);
            int end = ans.length();
            ans = new StringBuilder(ans.substring(1, end));
            ans.append(s);
            n--;
        }
        return ans.toString();
    }

    public static String LeftRotateString1(String str, int n) {
        if (str == null || str.equals("")) {
            return "";
        }
        int length = str.length();
        int tmp = n % length;
        return new StringBuilder().append(str.substring(tmp))
                .append(str.substring(0, tmp)).toString();
    }

    public static void main4(String[] args) {
        String s = "abcXYZdef";
        System.out.println(LeftRotateString(s, 3));
    }

    /**
     * 翻转单词序列
     *
     * @param str
     * @return
     */
    public String ReverseSentence(String str) {
        if (str == null || str.equals("")) {
            return "";
        }
        String[] strings = str.split(" ");
        StringBuilder ans = new StringBuilder();
        for (int i = strings.length - 1; i >= 0; i--) {
            ans.append(strings[i]);
            if (i > 0) {
                ans.append(" ");
            }
        }
        return ans.toString();
    }

    /**
     * 按之字形顺序打印二叉树
     *
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        if (pRoot == null) {
            return ans;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(pRoot);
        boolean flag = true;
        while (!stack.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            Queue<TreeNode> queue = new ArrayDeque<>();
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                list.add(cur.val);
                queue.add(cur);
            }
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                if (flag) {
                    if (cur.left != null) {
                        stack.add(cur.left);
                    }
                    if (cur.right != null) {
                        stack.add(cur.right);
                    }
                } else {
                    if (cur.right != null) {
                        stack.add(cur.right);
                    }
                    if (cur.left != null) {
                        stack.add(cur.left);
                    }
                }
            }
            flag = !flag;
            ans.add(list);
        }
        return ans;
    }

    /**
     * 给定一棵二叉搜索树，请找出其中的第k小的结点。
     * 例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
     *
     * @param pRoot
     * @param k
     * @return
     */
    public TreeNode KthNode(TreeNode pRoot, int k) {
        if (pRoot == null || k <= 0) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = pRoot;
        do {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            if (!stack.isEmpty()) {
                cur = stack.pop();
                k--;
                if (k == 0) {
                    return cur;
                }
                cur = cur.right;
            }
        } while (cur != null || !stack.isEmpty());
        return null;
    }

    /**
     * 1022. 从根到叶的二进制数之和
     *
     * @param root
     * @return
     */
    public static int sumRootToLeaf(TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        sumAllRootToLeaf(root, lists, list);
        int ans = 0;
        for (ArrayList<Integer> arrayList : lists) {
            StringBuilder str = new StringBuilder();
            for (Integer num : arrayList) {
                str.append(num);
            }
            String s = str.toString();
            if (s.equals("") || s == null) {
                continue;
            }
            ans += Integer.parseInt(s, 2);
        }
        return ans;
    }

    private static void sumAllRootToLeaf(TreeNode root, ArrayList<ArrayList<Integer>> lists, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        sumAllRootToLeaf(root.left, lists, list);
        sumAllRootToLeaf(root.right, lists, list);
        if (root.left == null && root.right == null) {
            lists.add(new ArrayList<>(list));
        }
        list.remove(list.size() - 1);
    }

    public static void main5(String[] args) {
        TreeNode root = new TreeNode(1);
        System.out.println(sumRootToLeaf(root));
    }

    /**
     * 209. 长度最小的子数组 - 滑动窗口
     *
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        while (start <= end && end < nums.length) {
            if (start == end) {
                if (nums[start] == target) {
                    ans = Math.min(ans, 1);
                    break;
                }
            }
            int tmp = 0;
            for (int i = start; i <= end; i++) {
                tmp += nums[i];
            }
            if (tmp == target) {
                ans = Math.min(ans, end - start + 1);
                start++;
            } else if (tmp < target) {
                end++;
            } else {
                ans = Math.min(ans, end - start + 1);
                start++;
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    public static int minSubArrayLen1(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = Math.min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    public static void main6(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        System.out.println(minSubArrayLen(11, nums));
    }

    /**
     * 904. 水果成篮
     *
     * @param fruits
     * @return
     */
    public static int totalFruit(int[] fruits) {
        int left = 0;
        int ans = 0;
        boolean flag = true;
        int flagLeft = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int right = 0; right < fruits.length; right++) {

            set.add(fruits[right]);
            if (set.size() == 2 && flag) {
                flag = false;
                flagLeft = right;
            }
            if (set.size() <= 2) {
                ans = Math.max(ans, right - left + 1);
                continue;
            }
            flag = true;
            right = flagLeft - 1;
            left = flagLeft;
            set.clear();
        }
        return ans;
    }

    public static void main7(String[] args) {
        int[] nums = {1, 0, 3, 4, 3};
        System.out.println(totalFruit(nums));
    }

    /**
     * 187. 重复的DNA序列
     *
     * @param s
     * @return
     */
    public List<String> findRepeatedDnaSequences(String s) {
        HashMap<String, Integer> map = new HashMap<>();
        List<String> list = new ArrayList<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String str = s.substring(i, i + 10);
            int tmp = map.getOrDefault(str, 0);
            if (tmp == 1) {
                list.add(str);
            }
            map.put(str, tmp + 1);
        }
        return list;
    }

    /**
     * 220. 存在重复元素 III
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int length = nums.length;
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < length; i++) {
            Long u = nums[i] * 1L;
            // 从 set 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
            Long l = set.floor(u);
            // 从 set 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
            Long r = set.ceiling(u);
            if (l != null && u - l <= t) {
                return true;
            }
            if (r != null && r - u <= t) {
                return true;
            }
            // 将当前数加到 set 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
            set.add(u);
            if (i >= k) {
                set.remove(nums[i - k] * 1L);
            }
        }
        return false;
    }

    public static void main8(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println(containsNearbyAlmostDuplicate(nums, 3, 0));
    }

    /**
     * 59. 螺旋矩阵 II
     *
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int row = 0;
        int col = 0;
        int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int index = 0;
        for (int i = 1; i <= Math.pow(n, 2); i++) {
            ans[row][col] = i;
            int nextRow = row + dir[index][0];
            int nextCol = col + dir[index][1];
            if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || ans[nextRow][nextCol] != 0) {
                index = (index + 1) % 4;
            }
            row = row + dir[index][0];
            col = col + dir[index][1];
        }
        return ans;
    }

    /**
     * 450. 删除二叉搜索树中的节点
     *
     * @param root
     * @param key
     * @return
     */
    public static TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.val == key) {
                root = remove(root, parent, cur);
                break;
            } else if (cur.val > key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        return root;
    }

    private static TreeNode remove(TreeNode root, TreeNode parent, TreeNode cur) {
        //情况1:cur.left = null
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
            return root;
        }
        //情况2:cur.right = null
        if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
            return root;
        }
        //情况3:cur的左右子树都不为空
        if (cur.left != null && cur.right != null) {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
        return root;
    }

    public static void main9(String[] args) {
        TreeNode root = new TreeNode(0);
        System.out.println(deleteNode(root, 0));
    }

    /**
     * 829. 连续整数求和
     *
     * @param n
     * @return
     */
    public static int consecutiveNumbersSum1(int n) {
        int ans = 0;
        n *= 2;
        for (int k = 1; k * k < n; k++) {
            if (n % k != 0) {
                continue;
            }
            if ((n / k - (k - 1)) % 2 == 0) {
                ans++;
            }
        }
        return ans;
    }

    public static int consecutiveNumbersSum(int n) {
        int left = 1;
        int right = 1;
        int ans = 0;
        while (left <= right) {
            if (right == n) {
                ans++;
                break;
            }
            int sum = ((left + right)) * (right - left + 1) / 2;
            if (sum == n) {
                ans++;
                left++;
            } else if (sum < n) {
                right++;
            } else {
                left++;
            }
        }
        return ans;
    }

    public static void main10(String[] args) {
        System.out.println(consecutiveNumbersSum(15));
    }


    /**
     * 929. 独特的电子邮件地址
     *
     * @param emails
     * @return
     */
    public int numUniqueEmails(String[] emails) {
        Set<String> set = new HashSet<>();
        for (String s : emails) {
            StringBuilder sb = new StringBuilder();
            int n = s.length();
            int i = 0;
            boolean flag = true;
            while (i < n) {
                char c = s.charAt(i);
                if (c == '@') {
                    break;
                }
                if (c == '.' && ++i >= 0) {
                    continue;
                }
                if (c == '+') {
                    flag = false;
                }
                if (flag) {
                    sb.append(c);
                }
                i++;
            }
            set.add(sb.append(s.substring(i)).toString());
        }
        return set.size();
    }

    /**
     * 478. 在圆内随机生成点-拒绝采样法
     */
    Random random;
    double xc, yc, r;

    public void Solution(double radius, double x_center, double y_center) {
        random = new Random();
        xc = x_center;
        yc = y_center;
        r = radius;
    }

    public double[] randPoint() {
        while (true) {
            double x = random.nextDouble() * (2 * r) - r;
            double y = random.nextDouble() * (2 * r) - r;
            if (x * x + y * y <= r * r) {
                return new double[]{xc + x, yc + y};
            }
        }
    }

    /**
     * 875. 爱吃香蕉的珂珂--二分查找
     * 从 1 -
     *
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        //int max = Arrays.stream(piles).max().getAsInt();
        int max = Integer.MIN_VALUE;
        for (Integer num : piles) {
            if (num > max) {
                max = num;
            }
        }
        int ans = max;
        int right = max;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int sumTime = 0;
            for (Integer pile : piles) {
                int curTime = pile / mid;
                if (pile % mid != 0) {
                    curTime++;
                }
                sumTime += curTime;
            }
            if (sumTime <= h) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 703. 数据流中的第 K 大元素
     *
     * @param k
     * @param nums
     */
    static PriorityQueue<Integer> queue;
    static int cur;

    public static void KthLargest(int k, int[] nums) {
        cur = k;
        queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        for (int a : nums) {
            if (queue.size() < k) {
                queue.add(a);
            } else {
                if (a > queue.peek()) {
                    queue.poll();
                    queue.add(a);
                }
            }
        }
    }

    public static int add(int val) {
        if (queue.size() < cur) {
            queue.add(val);
            return queue.peek();
        }
        if (queue.isEmpty()) {
            return 0;
        }
        if (val > queue.peek()) {
            queue.poll();
            queue.add(val);
        }
        return queue.peek();
    }

    public static void main11(String[] args) {
        int[] nums = {5, -1};
        int k = 3;
        KthLargest(k, nums);
        System.out.println(add(2));
        System.out.println(add(1));
        System.out.println(add(-1));
        System.out.println(add(3));
        System.out.println(add(4));
    }

    /**
     * 1894. 找到需要补充粉笔的学生编号-前缀和
     *
     * @param chalk
     * @param k
     * @return
     */
    public static int chalkReplacer(int[] chalk, int k) {
        long sum = 0;
        long[] nums = new long[chalk.length];
        for (int i = 0; i < chalk.length; i++) {
            sum += chalk[i];
            nums[i] = sum;
        }
        long round = k % sum;

        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > round) {
                ans = i;
                break;
            }
        }
        return ans;
    }

    public static void main12(String[] args) {
        int[] nums = {3, 4, 1, 2};
        System.out.println(chalkReplacer(nums, 25));
    }

    /**
     * 890. 查找和替换模式
     * 利用两个hashmap建立一对一的关系
     *
     * @param words
     * @param pattern
     * @return
     */
    public static List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> ans = new ArrayList<>();
        for (String s : words) {
            HashMap<Character, Character> map = new HashMap<>();
            HashMap<Character, Character> hashMap = new HashMap<>();
            int cur = 0;
            for (Character c : pattern.toCharArray()) {
                if (map.containsKey(c)) {
                    if (s.charAt(cur) != map.get(c)) {
                        break;
                    } else {
                        cur++;
                    }
                } else {
                    map.put(c, s.charAt(cur));
                    cur++;
                }
            }
            int tmp = 0;
            for (Character c : s.toCharArray()) {
                if (hashMap.containsKey(c)) {
                    if (pattern.charAt(tmp) != hashMap.get(c)) {
                        break;
                    } else {
                        tmp++;
                    }
                } else {
                    hashMap.put(c, pattern.charAt(tmp));
                    tmp++;
                }
            }
            if (cur == pattern.length() && tmp == cur) {
                ans.add(s);
            }
        }
        return ans;
    }

    public static void main13(String[] args) {
        String[] words = {"abc", "deq", "mee", "aqq", "dkd", "ccc"};
        String pattern = "abb";
        System.out.println(findAndReplacePattern(words, pattern));
    }

    /**
     * 1051. 高度检查器
     * 先复制一份;再将原来的数组排序;将排序前和排序后进行比较
     *
     * @param heights
     * @return
     */
    public int heightChecker(int[] heights) {
        int[] tmp = heights.clone();
        Arrays.sort(heights);
        int ans = 0;
        for (int i = 0; i < heights.length; i++) {
            if (tmp[i] != heights[i]) {
                ans++;
            }
        }
        return ans;
    }

    /**
     * 498. 对角线遍历
     *
     * @param mat
     * @return
     */
    public static int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int sum = n * m;
        int[] ans = new int[sum];
        if (mat.length == 0) {
            return ans;
        }
        int row = 0;
        int col = 0;
        int flag = 0;
        int rows = 1;
        int cols = 1;
        boolean re = false;
        ArrayList<Integer> lists = new ArrayList<>();
        while (flag < m + n) {
            flag++;
            ArrayList<Integer> list = new ArrayList<>();
            while (row >= 0 && col >= 0 && row < m && col < n) {
                list.add(mat[row][col]);
                row -= 1;
                col += 1;
            }
            if (re) {
                Collections.reverse(list);
                lists.addAll(list);
                re = false;
            } else {
                lists.addAll(list);
                re = true;
            }
            if (rows < m) {
                row = rows;
                rows++;
                col = 0;
            } else {
                row = m - 1;
                col = cols;
                cols++;
            }
        }
        for (int i = 0; i < lists.size(); i++) {
            ans[i] = lists.get(i);
        }
        return ans;
    }

    public static void main14(String[] args) {
        int[] arr = {0, 0, 0};
        duplicateZeros(arr);
    }

    /**
     * 1089. 复写零
     * 双指针
     *
     * @param arr
     */
    public static void duplicateZeros(int[] arr) {
        int length = arr.length;
        int[] ans = new int[length];
        int i = 0, j = 0;
        while (i < length && j < length) {
            if (arr[i] != 0) {
                ans[j] = arr[i];
                i++;
                j++;
            } else {
                ans[j] = 0;
                if (j + 1 < length) {
                    ans[j + 1] = 0;
                } else {
                    break;
                }
                j += 2;
                i++;
            }
        }
        for (int k = 0; k < length; k++) {
            arr[k] = ans[k];
        }
        System.out.println(ans);
    }


    ArrayList<Integer> list = new ArrayList<>();
    int sizes = 0;

    public double next(int val) {
        list.add(val);
        if (list.size() > 3) {
            list.remove(0);
        }
        int res = Math.min(list.size(), sizes);
        int sum = 0;
        for (Integer a : list) {
            sum += a;
        }
        return (sum * 1.0) / res;
    }

    /**
     * 565. 数组嵌套 -- 注意 A中不含有重复的元素
     * 简单模拟题
     *
     * @param nums
     * @return
     */
    public int arrayNesting(int[] nums) {
        int ans = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int cur = i;
            int tmp = 0;
            while (nums[cur] != -1) {
                tmp++;
                int res = nums[cur];
                nums[cur] = -1;
                cur = res;
            }
            ans = Math.max(ans, tmp);
        }
        return ans;
    }

    /**
     * 735. 行星碰撞 -利用栈
     *
     * @param asteroids
     * @return
     */
    public static int[] asteroidCollision(int[] asteroids) {
        Stack<HashMap<Integer, Integer>> stack = new Stack<>();
        int length = asteroids.length;
        int i = 0;
        while (i < length) {
            if (asteroids[i] < 0) {
                i++;
            } else {
                break;
            }
        }

        for (; i < length; i++) {
            if (asteroids[i] > 0) {
                HashMap<Integer, Integer> map = new HashMap<>();
                map.put(asteroids[i], i);
                stack.add(map);
            } else {
                while (!stack.isEmpty()) {
                    HashMap<Integer, Integer> tmp = stack.peek();
                    int cur = 0;
                    for (Map.Entry<Integer, Integer> entry : tmp.entrySet()) {
                        cur = entry.getKey();
                    }
                    if (cur > Math.abs(asteroids[i])) {
                        asteroids[i] = 0;
                        break;
                    } else if (cur < Math.abs(asteroids[i])) {
                        asteroids[tmp.get(cur)] = 0;
                        stack.pop();
                    } else {
                        asteroids[tmp.get(cur)] = 0;
                        asteroids[i] = 0;
                        stack.pop();
                        break;
                    }
                }
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int a : asteroids) {
            if (a != 0) {
                list.add(a);
            }
        }
        Integer[] ans = list.toArray(new Integer[list.size()]);
        return Arrays.stream(ans).mapToInt(Integer::valueOf).toArray();
    }

    public static void main15(String[] args) {
        int[] nums = {-2, 1, -1, -1};
        System.out.println(Arrays.toString(asteroidCollision(nums)));
    }

    public static void main16(String[] args) {
        int[][] arr = {{1, 2, 3}, {4, 5}, {6}};
        for (int x = 0; x < arr.length; x++) {
            for (int y = 0; y < arr[x].length; y++) {
                System.out.print(arr[x][y] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 1252. 奇数值单元格的数目
     *
     * @param m
     * @param n
     * @param indices
     * @return
     */
    public static int oddCells(int m, int n, int[][] indices) {
        int[][] nums = new int[m][n];
        for (int[] cur : indices) {
            for (int i = 0; i < n; i++) {
                nums[cur[0]][i]++;
            }
            for (int i = 0; i < m; i++) {
                nums[i][cur[1]]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (nums[i][j] % 2 != 0) {
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 814. 二叉树剪枝
     *
     * @param root
     * @return
     */
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left != null || root.right != null) {
            return root;
        }
        return root.val == 0 ? null : root;
    }

    /**
     * 1184. 公交站间的距离
     *
     * @param distance
     * @param start
     * @param destination
     * @return
     */
    public static int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int n = distance.length, i = start, j = start, a = 0, b = 0;
        while (i != destination) {
            a += distance[i];
            if (++i == n) {
                i = 0;
            }
        }
        while (j != destination) {
            if (--j < 0) {
                j = n - 1;
            }
            b += distance[j];
        }
        return Math.min(a, b);
    }

    public static void main(String[] args) {
        int[] nums = {3, 6, 7, 2, 9, 10, 7, 16, 11};
        System.out.println(distanceBetweenBusStops(nums, 6, 2));
    }
}

